#ifndef _BIT_STREAM_H_
#define _BIT_STREAM_H_

#include <vector>
#include <exception>

class BitStream
{
    private:
        typedef unsigned char T;

        unsigned char m_bits;           // this is for purpose of this class manipulation with bits
        unsigned char m_writtenBits;    // this is for user's info (flush does not afflict this)
        T m_item;
        std::vector<T> m_data;

    public:
        BitStream() { m_writtenBits = 0; m_bits = 0; m_item = 0; }
        unsigned int bits() const { return 8 * m_data.size() * sizeof(T) + m_bits; }
        unsigned int writtenBits() const { return m_writtenBits; };
        unsigned int bytes() const { return m_data.size() * sizeof(T) + (m_bits > 0); }
        void clear() { m_data.clear(); m_writtenBits = 0; m_bits = 0; m_item = 0; }
        const unsigned char * data() { flush(); return (const unsigned char *)m_data.data(); }
        void flush() { if(m_bits > 0) m_data.push_back(m_item); m_bits = 0; m_item = 0; }
        
        void add(int nbits, T val)	// nbits is number of bits counted from LSB (because of type casting)
        {
            static T tmp;
            static unsigned char space;
            //
            if(nbits > 8*sizeof(T)) throw std::exception("BitStream Exception: You can add max 8 bits per function call!");
            m_writtenBits += nbits;
            //
            space = 8*sizeof(T) - nbits;	// reuse the variable `space` for shift parameter
            val = ((val << space) >> space);	// shifts are there to make sure that bits higher than `nbits` are all 0 (it could be done by mask but it would had to be (pre)calculated)
            //
            space = 8*sizeof(T) - m_bits;	// space left in `m_item`
            if(nbits < space)
            {
                m_item |= (val << (space - nbits));
                m_bits += nbits;
            }
            else if(nbits > space)
            {
                tmp = val;
                m_bits = nbits - space;
                m_data.push_back(m_item | (val >> m_bits));	// remove bits that will not fit inside of the m_item and add the rest
                m_item = (tmp << (8*sizeof(T) - m_bits));
            }
            else	// nbits == space
            {
                m_data.push_back(m_item | val);
                m_item = 0;
                m_bits = 0;
            }
        }

        void pop_bit()	// pops the last bit of the stream
        {
            static unsigned char space;
            //
            if(m_bits == 0)
            {
                m_bits = 8*sizeof(T);
                m_item = m_data.back();
                m_data.pop_back();
            }
            space = 8*sizeof(T) - m_bits;	// space left in `m_item`
            space += 1;	// +1 for shifts -- it sets the last bit of the stream to 0
            m_item = ((m_item >> space) << space);
            --m_bits;
            --m_writtenBits;
        }

        BitStream & operator+=(const BitStream &bs)
        {
            for(size_t i = 0, im = bs.m_data.size(); i < im; i++)
                add(8*sizeof(T), bs.m_data[i]);
            add(bs.m_bits, ((bs.m_item) >> (8 - bs.m_bits)));	// shift, because add() takes bits from LSB
            return (*this);
        }

        static unsigned char bit_view(const unsigned char *stream, unsigned int pos)	// looks at `pos`th bit in the `stream` (starting from MSB)
        {
            unsigned char byte = stream[pos/8];
            byte >>= (7 - (pos % 8));
            return (unsigned char)(byte % 2);
        }
};

#endif	// _BIT_STREAM_H_